#include <vector>

using std::vector;
int CoinChange( vector<size_t>& nums, size_t amount )
{
    int            ret = -1;
    vector<size_t> dp  = vector<size_t>( amount + 1U, amount + 1U );
    dp[0]              = 0U;

    for ( size_t i = 1U; i < dp.size(); ++i ) {
        for ( auto coin : nums ) {
            if ( coin > i ) {
                continue;
            }
            dp[i] = std::min( dp[i], dp[i - coin] + 1 );
        }
    }

    if ( dp[amount] != amount + 1U ) {
        ret = dp[amount];
    }
    return ret;
}
